// Package _4_二叉搜索树的第k大节点 main
// @Title _4_二叉搜索树的第k大节点
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-01-16 18:45
// @Create  2022-01-16 18:45
package main

import "fmt"

//Definition for a binary 树 node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 中规中矩的做法
func kthLargest(root *TreeNode, k int) int {

	var recr func(root *TreeNode)
	var ans []int
	recr = func(node *TreeNode) {
		if node == nil {
			return
		}
		recr(node.Left)
		ans = append(ans, node.Val)
		recr(node.Right)
	}
	recr(root)
	return ans[len(ans)-k]
}

// 中规中矩的做法 提前返回
func kthLargestPlus(root *TreeNode, k int) int {
	var res int
	var recr func(root *TreeNode)
	recr = func(node *TreeNode) {
		if node == nil {
			return
		}
		recr(node.Right)
		if k == 0 {
			return
		}
		k -= 1
		if k == 0 {
			res = root.Val
		}
		recr(node.Left)
	}
	recr(root)
	return res
}

func main() {
	root := TreeNode{
		4,
		&TreeNode{
			2,
			&TreeNode{
				1,
				nil, nil,
			}, &TreeNode{
				3, nil, nil,
			},
		}, &TreeNode{
			7,
			&TreeNode{
				6,
				nil, nil,
			}, &TreeNode{
				9,
				nil, nil,
			},
		},
	}
	fmt.Println(kthLargest(&root, 8))
}
